﻿//85. 最大矩形
//给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。


class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        stack<int> sta;
        int ans = 0;
        int n = heights.size();
        for (int i = 0; i < n; i++)
        {
            //单调递增
            while (!sta.empty() && heights[sta.top()] > heights[i])
            {
                int h = heights[sta.top()];
                sta.pop();
                //left=sta.top()+1 i-1
                ans = max(ans, (i - sta.top() - 1) * h);
            }
            sta.push(i);
        }
        heights.erase(heights.begin());
        heights.erase(heights.end() - 1);
        return ans;
    }

    int maximalRectangle(vector<vector<char>>& matrix)
    {
        int ans = 0;
        int n = matrix[0].size();
        vector<int> arr(n, 0);
        for (auto& x : matrix)
        {
            for (int i = 0; i < n; i++)
            {
                arr[i] = x[i] == '1' ? arr[i] + 1 : 0;
            }
            ans = max(ans, largestRectangleArea(arr));
        }
        return ans;
    }
};